package graph;

import binary_heap.PriorityQueueGreater;

import java.util.*;

/**
 * 使用加强堆实现的Dijkstra算法优化版
 * <p>
 * 支持更新操作的优先队列，算法时间复杂度从O(nlogn)
 * 有意思的是经过 https://leetcode.cn/problems/minimum-weighted-subgraph-with-the-required-paths/submissions/ 题目的测试
 * 发现性能反而比系统堆低了不少，主要原因是系统堆是大佬写的，经过各种优化性能极致，我们自己写的堆比不了。
 * 其次题目的边数还不够多，更新操作降低树高后带来的性能提升不明显，加强堆底层还维护了索引表，导致常数时间较高，只有在边非常多的情况下才适合使用。
 *
 * @author lcw
 * @date 2023/12/11
 */
public class DijkstraGoodByHeapGreater {
    /**
     * 获取源点到图中任意点的最短距离
     *
     * @param node 源点
     */
    public static Map<Node<Integer>, Integer> dijkstra(Node<Integer> node) {
        Map<Node<Integer>, Integer> distMap = new HashMap<>();
        PriorityQueueGreater<NodeWithWeight<Integer>> q = new PriorityQueueGreater<>(
                Comparator.naturalOrder(), nodeWithWeight -> nodeWithWeight.node
        );
        distMap.put(node, 0);
        q.offer(new NodeWithWeight<>(node, 0));
        Set<Node<Integer>> freezeNodes = new HashSet<>();

        while (!q.isEmpty()) {
            NodeWithWeight<Integer> nd = q.poll();
            if (freezeNodes.contains(nd.node)) {
                continue;
            }
            freezeNodes.add(nd.node);

            for (Edge<Integer> nextEdge : nd.node.nextEdges) {
                int dist = distMap.get(nd.node) + nextEdge.weight;
                if (dist < distMap.getOrDefault(nextEdge.to, Integer.MAX_VALUE)) {
                    q.offer(new NodeWithWeight<>(nextEdge.to, dist));
                    distMap.put(nextEdge.to, dist);
                }
            }
        }

        return distMap;
    }

    private static final class NodeWithWeight<T> implements Comparable<NodeWithWeight<T>> {
        Node<T> node;
        Integer weight;

        public NodeWithWeight(Node<T> node, Integer weight) {
            this.node = node;
            this.weight = weight;
        }

        @Override
        public int compareTo(NodeWithWeight o) {
            return this.weight != o.weight ? this.weight - o.weight : this.node.hashCode() - o.node.hashCode();
        }
    }
}
